//给出一个区间的集合，请合并所有重叠的区间。 
//
// 
//
// 示例 1: 
//
// 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
//输出: [[1,6],[8,10],[15,18]]
//解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
// 
//
// 示例 2: 
//
// 输入: intervals = [[1,4],[4,5]]
//输出: [[1,5]]
//解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。 
//
// 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。 
//
// 
//
// 提示： 
//
// 
// intervals[i][0] <= intervals[i][1] 
// 
// Related Topics 排序 数组 
// 👍 581 👎 0

package leetcode.editor.cn;

//Java：合并区间
public class P56MergeIntervals {

    /**
     *
     * 思路：先排序第一个，然后比较第二个
     *
     * 执行用时： 94 ms , 在所有 Java 提交中击败了 5.02% 的用户 内存消耗： 42.5 MB , 在所有 Java 提交中击败了 48.01% 的用户
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {
            if (intervals.length == 0) {
                return new int[0][0];
            }
            int now = 0;
            sort(intervals);
            for (int j = 1; j < intervals.length; j++) {
                // 头个相同
                if (intervals[j][0] == intervals[now][0]) {
                    intervals[now][0] = intervals[j][0];
                    if (intervals[j][1] >= intervals[now][1]) {
                        intervals[now][1] = intervals[j][1];
                    }
                } else {
                    if (intervals[now][1] >= intervals[j][0]) {
                        intervals[now][1] = intervals[now][1] > intervals[j][1] ? intervals[now][1] : intervals[j][1];
                    } else {
                        now++;
                        intervals[now] = intervals[j];
                    }
                }
            }

            int[][] result = new int[now + 1][2];
            for (int i = 0; i <= now; i++) {
                result[i] = intervals[i];
            }
            return result;
        }


        // 按数组的第一个元素从小到大排序
        private void sort(int[][] intervals) {
            for (int i = 0; i < intervals.length; i++) {
                int min = i;
                for (int j = i + 1; j < intervals.length; j++) {
                    if (intervals[j][0] < intervals[min][0]) {
                        min = j;
                    }
                }
                swap(intervals, i, min);
            }
        }

        // 交换两个元素
        private void swap(int[][] intervals, int i, int k) {
            int[] temp = intervals[i];
            intervals[i] = intervals[k];
            intervals[k] = temp;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        // [[0,2],[2,3],[4,4],[0,1],[5,7],[4,5],[0,0]]
        int[][] nums = new int[][]{{0,2},{2,3},{4,4},{0,1},{5,7},{4,5},{0,0}};
        Solution solution = new P56MergeIntervals().new Solution();
        int[][] a = solution.merge(nums);
        System.out.println(a);
        // TO TEST
    }

}